//package leetcode.leetcode_138;
//
//import java.util.HashMap;
//
//class Node {
//    int val;
//    Node next;
//    Node random;
//
//    public Node(int val) {
//        this.val = val;
//        this.next = null;
//        this.random = null;
//    }
//}
//
//
//class Solution {
//    public Node copyRandomList(Node head) {
//        if (head == null) return null;
//        Node cur= head;
//        while(cur != null){
//            cur.next = new Node(cur.val,cur.next);
//            cur = cur.next.next;
//        }
////        计算新节点的随机值
//        cur = head;
//        while(cur!=null){
//            if (cur.random != null){
//                cur.next.random = cur.random.next;
//            }
//            cur = cur.next.next;
//        }
////        分离新旧节点
//        Node ans = head.next;
//        cur = head;
//        while(cur.next!=null){
//            ans.next = cur.next.next;
//            cur.next = cur.next.next;
//            cur = cur.next;
//        }
//        cur.next = null;
//        return ans;
//    }
//}